// 最好情况：O(n)，最坏情况：O(n^2)
export default function insertSort(arr: number[]): number[] {
  let n = arr.length;
  for (let i = 1; i < n; i++) {
    const temp = arr[i];
    let j = i - 1;
    while (temp < arr[j] && j >= 0) {
      arr[j + 1] = arr[j];
      j--;
    }
    arr[j + 1] = temp;
  }

  return arr;
}

console.log(insertSort([12, 232, 43, 12, 423, 1, 2, 3]));
